17677 - [1차] 뉴스 클러스터링
info
- 문제 보기: 17677 - [1차] 뉴스 클러스터링
- 소요 시간: 25분 49초
- 풀이 언어:
java
- 체감 난이도: 2️⃣~3️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
해시
풀이 코드
info
- 메모리: 92100 KB
- 시간: 14 ms
import java.util.*;
class Solution {
public int solution(String str1, String str2) {
// to lowercase
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();
// set
Map<String, Integer> A = new HashMap<>();
Map<String, Integer> B = new HashMap<>();
Map<String, Integer> I = new HashMap<>();
Map<String, Integer> U = new HashMap<>();
// init set
char[] s1Arr = str1.toCharArray();
char[] s2Arr = str2.toCharArray();
for (int i = 0; i < str1.length()-1; ++i)
if ('a' <= s1Arr[i] && s1Arr[i] <= 'z' && 'a' <= s1Arr[i+1] && s1Arr[i+1] <= 'z')
A.merge("" + s1Arr[i] + s1Arr[i+1], 1, Integer::sum);
for (int i = 0; i < str2.length()-1; ++i)
if ('a' <= s2Arr[i] && s2Arr[i] <= 'z' && 'a' <= s2Arr[i+1] && s2Arr[i+1] <= 'z')
B.merge("" + s2Arr[i] + s2Arr[i+1], 1, Integer::sum);
// get intersection
for (String k : A.keySet()) {
if (B.containsKey(k)) I.put(k, Math.min(A.get(k), B.get(k)));
}
// get union
for (String k : A.keySet()) {
U.put(k, B.containsKey(k) ? Math.max(A.get(k), B.get(k)) : A.get(k));
}
for (String k : B.keySet()) {
if (!U.containsKey(k)) U.put(k, B.get(k));
}
int a = I.values().stream().mapToInt(i->i).sum();
int b = U.values().stream().mapToInt(i->i).sum();
if (b == 0) return 65536;
return (int) (65536 * (double) a / b);
}
}
풀이 해설
해시맵을 이용하여 다중집합의 교집합, 합집합을 구하고, 최종적으로 자카드 유사도를 계산하는 문제이다.
✖️ 교집합
A, B 양 쪽에 모두 존재할때만 min value를 넣는다.
for (String k : A.keySet()) {
if (B.containsKey(k)) I.put(k, Math.min(A.get(k), B.get(k)));
}
➕ 합집합
- A에만 있으면 A value로 넣는다.
- A, B 모두에 있으면 max value로 넣는다.
- B에 있으면서 1,2에서 확인하지 않은(=B에만 있는) 값은 B value로 넣는다.
for (String k : A.keySet()) {
U.put(k, B.containsKey(k) ? Math.max(A.get(k), B.get(k)) : A.get(k));
}
for (String k : B.keySet()) {
if (!U.containsKey(k)) U.put(k, B.get(k));
}
메모
- 무난한 난이도
- 막줄
a
,b
네이밍 별로인듯..ni
,nu
가 직관적이고 나을듯